package com.lwx.algorithm.chapter6;

import com.lwx.util.ListNode;

/**
 * k个有序列表合并
 */
public class Offer23 {
    public static void main(String[] args) {
        Offer23 o = new Offer23();
        ListNode l11 = new ListNode(1);
        ListNode l12 = new ListNode(4);
        ListNode l13 = new ListNode(5);
        l11.setNext(l12);
        l12.setNext(l13);
        ListNode l21 = new ListNode(1);
        ListNode l22 = new ListNode(3);
        ListNode l23 = new ListNode(4);
        l21.setNext(l22);
        l22.setNext(l23);
        ListNode[] listNodes = {l11,l21};
        ListNode listNode = o.mergeKLists(listNodes);
        ListNode currentNode = listNode;
        while (currentNode != null){
            System.out.print(currentNode.getVal() + "->");
            currentNode = currentNode.getNext();
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ret = null;
        if(lists == null || lists.length == 0){
            return null;
        }
        for (int i = 0; i < lists.length; i++) {
            ret = mergeTwoLists(ret,lists[i]);
        }
        return ret;
    }

    /**
     * 将两个有序列表合并为一个有序列表
     * @param a
     * @param b
     * @return
     */
    public ListNode mergeTwoLists(ListNode a, ListNode b){
        if(a == null || b == null){
            return a == null? b:a;
        }
        /**
         * head为虚节点，返回时返回head的下一个节点
         */
        ListNode head = new ListNode();
        ListNode tail = head;
        ListNode aPtr = a;
        ListNode bPtr = b;
        while (aPtr != null && bPtr != null){
            if(aPtr.getVal() <= bPtr.getVal()){
                tail.setNext(aPtr);
                tail = aPtr;
                aPtr = aPtr.getNext();
            }else {
                tail.setNext(bPtr);
                tail = bPtr;
                bPtr = bPtr.getNext();
            }
        }
        //这两步没有必要，链表后面的数据没有断
        if(aPtr == null){
            tail.setNext(bPtr);
        }
        if(bPtr == null){
            tail.setNext(aPtr);
        }
        return head.getNext();
    }
}
